package lee.study.TestSort;


import java.util.Arrays;

public class mergeSort {
    //merge用来归并
    public static void merge(int[] array, int low, int mid, int high) {
        int s1 = low;
        int s2 = mid + 1;
        int[] ret = new int[high - low + 1];
        int i = 0;//用来表示ret数组的下标

        while (s1 <= mid && s2 <= high) {
            if (array[s1] <= array[s2]) {
                ret[i++] = array[s1++];
            } else {
                ret[i++] = array[s2++];

            }
        }
        while (s1 <= mid) {//必须是循环而不是if
            ret[i++] = array[s1++];
        }
        while (s2 <= high) {
            ret[i++] = array[s2++];
        }

        for (int j = 0; j < ret.length; j++) {
            array[j + low] = ret[j];
        }
    }

    public static void mergeSortInternal(int[] array, int low, int high) {
        if (low == high) {
            return;
        }
        int mid = (low + high) / 2;

        //分解
        mergeSortInternal(array, low, mid);
        mergeSortInternal(array, mid + 1, high);
        //归并
        merge(array, low, mid, high);

    }

    //时间复杂度：O（n*log2n）可以看做一个二叉树
    //空间复杂度：O（n）
    //稳定性：是一个稳定性的排序。
    public static void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
    int[] array={1,6,3,8,2,9,11,75,23};
    mergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
